1. Field of the Invention
The present invention relates to a code decoding apparatus. In particular, the present invention relates to a variable-length code decoding apparatus, a method for variable-length code decoding, and a program for causing a computer to perform the method.
2. Description of the Related Art
Variable-length codes for compression purposes are, like Huffman codes, designed to assign code words with shorter code lengths to pieces of information that occur more frequently. Since the pieces of information that occur more frequently are represented by shorter codes, the number of pieces of data that are represented by long codes is not large, and on average, data coded is smaller in size than the data in its original form, i.e., data compression is achieved. Thus, in the case of the variable-length codes, it takes shorter to decode codes with higher frequencies and longer to decode codes with lower frequencies, which shortens the average decoding time. Moreover, the codes with greater frequencies have shorter code lengths, and can therefore be represented with fewer bits.
A variable-length code decoding apparatus can be implemented in a very small size, by forming a code table with a combinational circuit. Forming the code table with the combinational circuit, however, requires that the code table be fixed. In contrast, code tables are sometimes stored in a memory in order to allow subsequent support of various code tables. The simplest mode of storing the code table in the memory is to store all pairs of code values and code lengths. However, when a fixed number of bits is allocated to both the code values and the code lengths, a relatively large capacity is required, and in addition, retrieval need be done by reading and examining each code value and code length. While a time for the retrieval can be reduced by sorting the data by code length or the like, several cycles are still required. Use of an associative memory or the like is conceivable as a way of accomplishing the retrieval with fewer cycles, but that will involve a problem of an increase in circuit area.
Another conceivable mode is to store only the code lengths of the code words in the memory while arranging for the code values to coincide with offset addresses of the memory. In this mode, code values whose code length is shorter compared to the number of bits of the address are stored on the most significant bit (MSB) side, while low-order bits of the same code length are stored redundantly as an address indicating that code word. This has an advantage in that the retrieval can be accomplished instantly using the code values, but the memory needs to have an address bit corresponding to a maximum code length. The longer the address bit is, the larger amount of redundant data is involved.
As such, a decoding apparatus has been proposed that does not store the entire code table but stores, for each code length, the maximum code value and an offset address for decoding information corresponding thereto (see Japanese Patent Laid-open No. Hei 6-104769 (FIG. 1), for example). In this related art technique, without the code lengths being stored, the maximum value of the code lengths is stored at a location whose unit number or address corresponds to the code length. Then, decoding operations corresponding to a plurality of code lengths are performed at a time, in order to shorten the decoding time.